<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
// Dinic's algorithm + scaling
// Not more than 0.08 sec on all tests

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;
#include &lt;cassert&gt;
#include &lt;iostream&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)

typedef long long ll;

#define maxv 503
#define maxe 20010

int e = 2, n, m, he[maxv], ne[maxe], to[maxe], c[maxe], c0[maxe];
int cc, u[maxv], d[maxv], che[maxv];
int qst, qen, q[maxv];

ll res = 0;
int gmi, K;

int dfs( int v, int cmi )
{
  if (v == n)
  {
    gmi = cmi;
    return 1;
  }
  u[v] = cc;
  while (che[v])
  {
    int x, i = che[v];
    if (d[x = to[i]] == d[v] + 1 && c[i] &gt;= K)
      if (u[x] != cc && dfs(x, min(cmi, c[i])))
      { 
        c[i] -= gmi, c[i ^ 1] += gmi;
        return 1;       
      }
    che[v] = ne[che[v]];
  }
  return 0;
}

int cnt1 = 0, cnt2 = 0;

int Phase()
{
  cc++;
  qst = qen = 0;
  q[qen++] = 1, u[1] = cc, d[1] = 0;
  while (qst &lt; qen)
  {
    int x, v = q[qst++];
    for (int i = he[v]; i; i = ne[i])
      if (c[i] &gt;= K && u[x = to[i]] != cc)
      {
        u[x] = cc, d[x] = d[v] + 1;
        q[qen++] = x;
      }
  }
  if (u[n] != cc)
    return 0;

  memcpy(che, he, sizeof(he));
  cc++;
  while (dfs(1, (int)2e9))
  {
    cnt2 += d[n], cnt1++;
    res += gmi, cc++;
  }
  return 1;
}

int main()
{
  freopen("flow2.in", "r", stdin);
  freopen("flow2.out", "w", stdout);

  assert(scanf("%d%d", &n, &m) == 2);
  assert(1 &lt;= n && n &lt;= 500);
  assert(1 &lt;= m && m &lt;= 10000);
  forn(i, m)
  {
    int a, b, _c;
    assert(scanf("%d%d%d", &a, &b, &_c) == 3);
    c0[i] = _c;
    assert(1 &lt;= a && a &lt;= n);
    assert(1 &lt;= b && b &lt;= n);
    assert(1 &lt;= _c && _c &lt;= (int)1e9);
    ne[e] = he[a], to[e] = b, c[e] = _c, he[a] = e++;
    ne[e] = he[b], to[e] = a, c[e] = 0, he[b] = e++;
  }

  memset(u, 0, sizeof(u)), cc = 1;
  for (K = (1 &lt;&lt; 30); K &gt; 0; K &gt;&gt;= 1)
    while (Phase())
      ;

  fprintf(stderr, "cnt1=%d\n", cnt1);
  fprintf(stderr, "cnt2=%d\n", cnt2);

  cout &lt;&lt; res &lt;&lt; endl;
  forn(i, m)
    printf("%d\n", c0[i] - c[2 * i + 2]);
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
